package org.example.dp.knapsack;

import java.util.Arrays;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/05/16 21:05
 */
@Deprecated
public class Solution322 {
    int[] mem;

    public static void main(String[] args) {
        Solution322 solution322 = new Solution322();
        int[] coins = new int[]{186,419,83,408};
        int amount = 6249;
        System.out.println(solution322.coinChange(coins, amount));
    }

    public int coinChange(int[] coins, int amount) {
        if(amount == 0){
            return 0;
        }

        boolean flag = false;
        for(int i : coins){
            if(amount >= i){
                flag = true;
                break;
            }
        }

        if(!flag){
            return -1;
        }

        mem = new int[amount+1];
        Arrays.fill(mem, Integer.MAX_VALUE);

        int way = findMiniWay(coins , amount);
        return way;
    }

    private int findMiniWay(int[] coins, int amount) {
        if(mem[amount] < Integer.MAX_VALUE){
            return mem[amount];
        }

        int way = -1;
        for(int i : coins){
            if(i == amount){
               way = 1;
               mem[amount] = way;
            }else if(amount > i){
                int sub = findMiniWay(coins, amount-i);
                if(sub > 0 ){
                    sub++;
                }
               way = Math.min(sub, mem[amount]);
               mem[amount] = way;
            }
        }

        System.out.println(amount + "，" + way);
        return way;
    }

    //动态规划 可兑换的最大值
    public int coinChange2(int[] coins, int amount) {
        if(amount == 0){
            return 0;
        }

        int[][] dp = new int[coins.length+1][amount+1];
        for(int i=1;i<=coins.length;i++){
            int w = coins[i-1];
            int v = coins[i-1];
            for(int j=1;j<=amount;j++){
                if(j>=w){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-w] + v);
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[coins.length][amount];
    }

}
